Search for: All records

Quantum control aims to manipulate quantum systems toward specific quantum states or desired operations. Designing highly accurate and effective control steps is vitally important to various quantum applications, including energy minimization and circuit compilation. In this paper we focus on discrete binary quantum control problems and apply different optimization algorithms and techniques to improve computational efficiency and solution quality. Specifically, we develop a generic model and extend it in several ways. We introduce a squared$L_2$-penalty function to handle additional side constraints, to model requirements such as allowing at most one control to be active. We introduce a total variation (TV) regularizer to reduce the number of switches in the control. We modify the popular gradient ascent pulse engineering (GRAPE) algorithm, develop a new alternating direction method of multipliers (ADMM) algorithm to solve the continuous relaxation of the penalized model, and then apply rounding techniques to obtain binary control solutions. We propose a modified trust-region method to further improve the solutions. Our algorithms can obtain high-quality control results, as demonstrated by numerical studies on diverse quantum control examples.

 

The outbreak of coronavirus disease 2019 (COVID-19) has led to significant challenges for schools and communities during the pandemic, requiring policy makers to ensure both safety and operational feasibility. In this paper, we develop mixed-integer programming models and simulation tools to redesign routes and bus schedules for operating a real university campus bus system during the COVID-19 pandemic. We propose a hub-and-spoke design and utilize real data of student activities to identify hub locations and bus stops to be used in the new routes. To reduce disease transmission via expiratory aerosol, we design new bus routes that are shorter than 15 minutes to travel and operate using at most 50% seat capacity and the same number of buses before the pandemic. We sample a variety of scenarios that cover variations of peak demand, social distancing requirements, and bus breakdowns to demonstrate the system resiliency of the new routes and schedules via simulation. The new bus routes were implemented and used during the academic year 2020–2021 to ensure social distancing and short travel time. Our approach can be generalized to redesign public transit systems with a social distancing requirement to reduce passengers’ infection risk. History: This paper was refereed. This article has been selected for inclusion in the Special Issue on Analytics Remedies to COVID-19. Funding: This work was supported by the National Science Foundation [Grant CMMI-2041745] and the University of Michigan, College of Engineering. 

Amidst the COVID-19 pandemic, restaurants become more reliant on no-contact pick-up or delivery ways for serving customers. As a result, they need to make tactical planning decisions such as whether to partner with online platforms, to form their own delivery team, or both. In this paper, we develop an integrated prediction-decision model to analyze the profit of combining the two approaches and to decide the needed number of drivers under stochastic demand. We first use the susceptible-infected-recovered (SIR) model to forecast future infected cases in a given region and then construct an autoregressive-moving-average (ARMA) regression model to predict food-ordering demand. Using predicted demand samples, we formulate a stochastic integer program to optimize food delivery plans. We conduct numerical studies using COVID-19 data and food-ordering demand data collected from local restaurants in Nuevo Leon, Mexico, from April to October 2020, to show results for helping restaurants build contingency plans under rapid market changes. Our method can be used under unexpected demand surges, various infection/vaccination status, and demand patterns. Our results show that a restaurant can benefit from partnering with third-party delivery platforms when (i) the subscription fee is low, (ii) customers can flexibly decide whether to order from platforms or from restaurants directly, (iii) customers require more efficient delivery, (iv) average delivery distance is long, or (v) demand variance is high. 

We consider a variant of the vehicle routing problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation-based linear-programming relaxation for this VRP. Specifically, we focus on algorithms for the “pricing problem,” which corresponds to the resource-constrained elementary shortest path problem. The first algorithm extends the pulse algorithm for which we derive a new bounding scheme on the maximum load of any route. The second algorithm is based on random coloring from parameterized complexity which can be also combined with other techniques in the literature for improving VRPs, including cutting planes and column enumeration. We conduct numerical studies using VRP benchmarks (with 50–957 nodes) and instances of a medical home care delivery problem using census data in Wayne County, Michigan. Using parallel computing, both pulse and random coloring can significantly improve column generation for solving the linear programming relaxations and we can obtain heuristic integer solutions with small optimality gaps. Combining random coloring with column enumeration, we can obtain improved integer solutions having less than 2% optimality gaps for most VRP benchmark instances and less than 1% optimality gaps for the medical home care delivery instances, both under a 30-minute computational time limit. The use of cutting planes (e.g., robust cuts) can further reduce optimality gaps on some hard instances, without much increase in the run time. Summary of Contribution: The vehicle routing problem (VRP) is a fundamental combinatorial problem, and its variants have been studied extensively in the literature of operations research and computer science. In this paper, we consider general-purpose algorithms for solving VRPs, including the column-generation approach for the linear programming relaxations of the integer programs of VRPs and the column-enumeration approach for seeking improved integer solutions. We revise the pulse algorithm and also propose a random-coloring algorithm that can be used for solving the elementary shortest path problem that formulates the pricing problem in the column-generation approach. We show that the parallel implementation of both algorithms can significantly improve the performance of column generation and the random coloring algorithm can improve the solution time and quality of the VRP integer solutions produced by the column-enumeration approach. We focus on algorithmic design for VRPs and conduct extensive computational tests to demonstrate the performance of various approaches. 

In this paper, we consider an integrated vehicle routing and service scheduling problem for serving customers in distributed locations who need pick-up, drop-off, or delivery services. We take into account the random trip time, nonnegligible service time, and possible customer cancellations, under which an ill-designed schedule may lead to undesirable vehicle idleness and customer waiting. We build a stochastic mixed-integer program to minimize the operational cost plus expected penalty cost of customers’ waiting time, vehicles’ idleness, and overtime. Furthermore, to handle real-time arrived service requests, we develop K-means clustering-based algorithms to dynamically update planned routes and schedules. The algorithms assign customers to vehicles based on similarities and then plan schedules on each vehicle separately. We conduct numerical experiments based on diverse instances generated from census data and data from the Ford Motor Company’s GoRide service, to evaluate result sensitivity and to compare the in-sample and out-of-sample performance of different approaches. Managerial insights are provided using numerical results based on different parameter choices and uncertainty settings.